package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20241103;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Leetcode3342 {

    /**
     * 到达最后一个房间的最少时间II
     * @param moveTime
     * @return
     */
    static int[][] dirs={{-1,0},{1,0},{0,-1},{0,1}};
    public int minTimeToReach(int[][] moveTime){
        int n=moveTime.length,m=moveTime[0].length;
        int[][] times=new int[n][m];
        for(int i=0;i<n;i++){
            Arrays.fill(times[i],Integer.MAX_VALUE);
        }
        times[0][0]=0;
        PriorityQueue<int[]> pq=new PriorityQueue<int[]>((a,b)->a[2]-b[2]);// 根据时间构建的小根堆
        pq.offer(new int[]{0,0,0});
        while(!pq.isEmpty() && times[n-1][m-1]==Integer.MAX_VALUE){
            int[] cell=pq.poll();
            int row=cell[0],col=cell[1],time=cell[2];
            if(times[row][col]<time){
                continue;
            }
            for(int[] dir : dirs){
                int newRow=row+dir[0],newCol=col+dir[1];
                if(newRow>=0 && newRow<n && newCol>=0 && newCol<m){
                    int newTime=Math.max(time,moveTime[newRow][newCol])+(row+col)%2+1;
                    if(newTime<times[newRow][newCol]){
                        times[newRow][newCol]=newTime;
                        pq.offer(new int[]{newRow,newCol,newTime});
                    }
                }
            }
        }
        return times[n-1][m-1];
    }
}
